/*
dp[i][j]表示s[i.....j]是否是回文
状态转移方程：dp[i][j]=(s[i]==s[j])and dp[i+1][j-1]
边界条件 j-i<3;即如果s[i]==s[j]&&j-i<3,dp[i][j]=1;
*/
class Solution {
public:
    int getLongestPalindrome(string s, int n) {
        // write code here
        if(n<2)
            return 1;
        int maxlen=1;
        vector<vector<int>>dp(n,vector<int>(n,0));
        //单个字符一定是回文串，所以对角线一定为true
        for(int i=0;i<n;i++)
            dp[i][i]=1;
        //j表示行 i表示列
        //由于dp[i][j]需要参考他左下方的值
        //因此先升序填列
        //后升序填行
        for(int j=1;j<n;j++)
        {
            for(int i=0;i<j;i++)
            {
                if(s[i]!=s[j])
                    dp[i][j]=0;
                else{
                    if(j-i<3)
                        dp[i][j]=1;
                    else
                        dp[i][j]=dp[i+1][j-1];
                }
                if(dp[i][j]==1&&j-i+1>maxlen)
                {   
                    maxlen=j-i+1; 
                }
            }
        }
       return maxlen;
    }
};